package org.aplombh.java.study.dp;

import java.lang.reflect.Array;
import java.util.Arrays;

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci(10) + fibonacci(9));
        System.out.println(dpFibonacci(10) + dpFibonacci(9));
    }

    private static final int[] f1 = new int[99];
    private static final int[] f2 = new int[99];

    static {
        Arrays.fill(f1, -1);
        Arrays.fill(f2, -1);
        f1[0] = f2[0] = 0;
        f1[1] = f2[1] = 1;
    }

    private static int fibonacci(int n) {
        for (int i = 2; i <= n; i++) {
            f1[i] = f1[i - 1] + f1[i - 2];
        }
        return f1[n];
    }

    private static int dpFibonacci(int n) {
        if (f2[n] == -1)
            f1[n] = dpFibonacci(n - 1) + dpFibonacci(n - 2);
        return f1[n];
    }
}
